﻿#include"function.h"
bool myStrcmp(string target, string gto)
{
	if (target.size() != gto.size())
		return false;
	for (unsigned int i = 0; i < target.size(); i++)
	{
		if (target.at(i) != gto.at(i))
			return false;
	}
	return true;
}

int locate_vertexByName(AdjGraph* G, string name)
{
	int len = G->adjlist.size();
	for (int i = 0; i < len; i++) {
		if (G->adjlist[i].data.name == name) {
			return i;
		}
	}
	return -1;
}

int locate_vertexByEqInfo(AdjGraph*& G, string eq_name)
{
	int len = G->adjlist.size();
	for (int i = 0; i < len; i++) {
		for (auto t : G->adjlist[i].data.eq_info) {
			if (t == eq_name)
				return i;
		}
	}
	return -1;
}

VNode new_building(AdjGraph*& G,int t_idx)
{
	VNode p;
	p.count = 0;
	p.firstarc = NULL;
	p.data.R_level = 0;
	string name_;

	//这里需要加一个辅助方法，判断是否名字重复，建筑内的配备可以重复
	//但是我只想修改目标建筑物的配备，那么这个名字可以重复 特判一下
	while (true) {
		cout << "请输入该建筑物的名字:";
		cin >> name_;
		int idx = locate_vertexByName(G, name_);
		if (idx != -1 && idx != t_idx) {
			cout << "该名字已被占用！！！ 请重试" << endl;
			continue;
		}
		else {
			break;
		}
	}
	p.data.name = name_;

	while (true) {
		string info, choice;
		cout << "请输入配备信息:";
		cin >> info;
		p.data.eq_info.push_back(info);
		cout << "添加成功!" << endl;
		//判断是否添加完毕
		cout << "是否以及添加完毕，若是，则输入yes，否则输入其它 !" << endl;
		cin >> choice;
		//if (info.compare("yes")) break;    //本来的这个compare函数不好满足需求，会返回负数 正数 相等返回0
		if (myStrcmp(choice, "yes")) break;
	}

	double grade;
	cout << "请输入你觉得这个建筑的推荐指数：";
	cin >> grade;
	p.data.R_level = grade;
	return p;
};


bool add_building(AdjGraph*& G)
{
	bool flag = true;
	cout << "接下来请输入第" << G->ver_num + 1 << "号建筑的相关信息" << endl;
	VNode p = new_building(G);
	p.firstarc = nullptr;
	//找到位置，并加入
	//下标即编号
	G->adjlist.push_back(p);
	G->ver_num++;
	cout << "添加建筑物成功!!!" << endl;
	cout << "您新添加的建筑物信息如下：" << endl;
	print_Onebuilding(G, G->adjlist.size() - 1);
	//system("pause"); 不要忘了加
	return true;
}


bool locate_edgeById(AdjGraph* G, int idx1, int idx2) {
	//保险，万一是单行道  
	ArcNode* p = G->adjlist[idx1].firstarc, * q = G->adjlist[idx2].firstarc;
	while (p != nullptr) {
		if (p->adjvex == idx2) {
			cout << "已经存在这条边" << endl;
			return false;
		}
		p = p->nextarc;
	}
	while (q != nullptr) {
		if (q->adjvex == idx1) {
			cout << "已经存在这条边" << endl;
			return false;
		}
		q = q->nextarc;
	}
	//不存在这条边
	return true;
}


bool add_edge(AdjGraph*& G)
{
	string st, ed;
	int  n, m;
	while (true) {
		cout << "请输入要在哪两个地点之间插入边：";
		cin >> st >> ed;

		n = locate_vertexByName(G, st);
		m = locate_vertexByName(G, ed);

		if (n == m || n == -1 || m == -1 || G->adjlist.size() < n || G->adjlist.size() < m || !locate_edgeById(G, n, m)) {
			cout << "输入有误，请重新输入！" << endl;
			continue;//这个非常重要，不然后面是有可能爆炸的，越界访问
		}
		if (locate_edgeById(G, n, m)) {
			break;
		}
	}
	ArcNode* p = new ArcNode, * q = new ArcNode;
	p->adjvex = m, q->adjvex = n;// n---m ,m---n
	double len;
	while (true) {
		cout << "请输入要添加的这条道路的长度:";
		cin >> len;
		if (len < 0 || int(len) == 0) {
			cout << "输入有误，请重新输入！" << endl;
		}
		else {
			break;
		}
	}
	//头插法添加  邻接表类型要添加二次
	p->weight = q->weight = int(len);
	p->nextarc = G->adjlist[n].firstarc;
	G->adjlist[n].count++;
	G->adjlist[n].firstarc = p;
	q->nextarc = G->adjlist[m].firstarc;
	G->adjlist[m].firstarc = q;
	G->adjlist[m].count++;//出度++;
	cout << "添加边完成" << endl;
	return true;
}

void del_buildings(AdjGraph*& G)
{
	char choice='0';
	int idx = -1;
	string idx_name;
	cout << "请选择删除模式：(1---输入建筑物号数删除，2---输入建筑物名字删除,3---退出删除)" << endl;
	while (true) {
		cin >> choice;
		if (choice == '1' || choice == '2') {
			break;
		}
		else if (choice == '3') {
			cout << "退出删除模式" << endl;
			return;
		}
		cout << "输入有误,请重新输入!" << endl;
	}
	if (choice == '1') {
		while (true) {
			cout << "请输入你要删除的建筑物号数（从1号开始):";
			cin >> idx;
			idx--;//下标从0开始
			if (idx<0 || idx > int(G->adjlist.size() - 1)) {
				cout << "输入号数有误，请重新输入" << endl;
			}
			else {
				break;
			}
		}
	}
	else if (choice == '2') {
		while (true) {
			cout << "请输入你要删除的建筑物名字（注意不要输错！):";
			cin >> idx_name;
			idx = locate_vertexByName(G, idx_name);
			if (idx == -1) {
				cout << "输入有误，请重新输入!" << endl;
				continue;
			}
			else
			{
				break;
			}
		}
	}
	//删除步骤
	if (idx == -1) {
		cout << "删除下标不存在！" << endl;
		return;
	}
	VNode del_node = G->adjlist[idx];
	ArcNode* q, * r = NULL, * p = G->adjlist[idx].firstarc;
	G->adjlist.erase(G->adjlist.begin() + idx);
	//删除与被删顶点相关联的边信息
	while (p != nullptr) {
		q = p->nextarc;
		delete p;
		p = q;
	}
	for (int i = 0; i < G->adjlist.size(); i++) {
		p = G->adjlist[i].firstarc;
		while (p != nullptr) {
			if (p->adjvex == idx) {
				if (p == G->adjlist[i].firstarc) {
					G->adjlist[i].firstarc = p->nextarc;
				}
				else {
					if (r != nullptr) {
						r->nextarc = p->nextarc;
					}
					else {
						cout << "空指针异常,即将返回主界面" << endl;
						return;
					}
				}
				q = p;
				p = p->nextarc;
				delete q;
				G->edge_num--;
			}
			else {
				if (p->adjvex > idx) {
					p->adjvex--;
				}
				r = p;//r才是p真正意义上的前驱结点
				p = p->nextarc;
			}
		}
	}
	G->ver_num--;
	cout << "删除第" << idx + 1 << "号建筑物:" << del_node.data.name << "成功!" << endl;
}

void del_edge(AdjGraph*& G)
{
	string idx1, idx2;
	cout << "请输入你要删除的边所在的二个地点:";
	cin >> idx1 >> idx2;
	int st = locate_vertexByName(G, idx1);
	int ed = locate_vertexByName(G, idx2);
	if (st == -1 || ed == -1) {
		cout << "不存在这样的二个地点,输入有误" << endl;
		cout << "即将返回操作界面" << endl;
		return;
	}

	//直接开始删除,检查一下
	if (!locate_edgeById(G, st, ed)) {
		cout << "开始删除！...." << endl;
		ArcNode* p = G->adjlist[st].firstarc, * q = G->adjlist[ed].firstarc;
		ArcNode* pre = p;
		int weight_=0;
		while (p != nullptr) {
			if (G->adjlist[st].firstarc->adjvex == ed) {
				G->adjlist[st].firstarc = p->nextarc;
				weight_ = G->adjlist[st].firstarc->weight;//边的权值
				G->edge_num--;
				G->adjlist[st].count--;
				delete p;
				break;
			}
			if (p->adjvex == ed) {//这个时候必然不会是第一个点
				if (pre != NULL)//要想解决什么非空指针风险，就得判断它不为NULL
					pre->nextarc = p->nextarc;
				weight_ = p->weight;
				G->edge_num--;
				G->adjlist[st].count--;
				delete p;
				break;
			}
			pre = p;
			p = p->nextarc;
		}
		pre = q;
		while (q != nullptr) {
			if (G->adjlist[ed].firstarc->adjvex == st) {
				G->adjlist[ed].firstarc = q->nextarc;
				G->edge_num--;
				G->adjlist[ed].count--;
				delete q;
				break;
			}
			if (q->adjvex == st) {//这个时候必然不会是第一个点
				pre->nextarc = q->nextarc;
				G->edge_num--;
				G->adjlist[ed].count--;
				delete q;
				break;
			}
			pre = q;
			q = q->nextarc;
		}
		cout << "删除从" << idx1 << "到" << idx2 << "权值为"<<weight_ <<"的边成功！" << endl;
	}
	else {
		cout << "不存在这样的边，即将返回选择界面" << endl;
	}
}

void print_Onebuilding(AdjGraph* G, int idx)
{
	const Vnode& p = G->adjlist[idx];
	cout << "第" << idx + 1 << "号建筑物名字是:" << p.data.name << endl;
	//打印星星
	cout << "推荐指数：";
	//int cnt=p.data.R_level  先不改   ☆★
	int cnt_int = int(p.data.R_level);
	int cnt_float = ceil(p.data.R_level) - cnt_int;
	for (int k = 0; k < cnt_int; k++)
		cout << "★";
	if (cnt_float == 1) cout << "☆";
	cout << endl;
	if (!p.data.eq_info.empty()) {
		cout << "它主要配备有：" << endl;
		for (auto t : p.data.eq_info) {
			cout << t << endl;
		}
	}
}

void change_buildings(AdjGraph*& G)
{
	string t_name;
	int t_idx;
	while (true) {
		cout << "请输入你想要修改的建筑物名字:";
		cin >> t_name;
		t_idx = locate_vertexByName(G, t_name);
		if (t_idx == -1) {
			cout << "你的名字输入有误，查无此建筑" << endl;
			continue;
		}
		else {
			cout << "已查询到该建筑信息如下:" << endl;
			print_Onebuilding(G, t_idx);
			break;
		}
	}
	//输入修改信息
	cout << "接下来请输入修改信息:" << endl;
	VNode new_node = new_building(G,t_idx);
	new_node.firstarc = G->adjlist[t_idx].firstarc;
	G->adjlist[t_idx] = new_node;
	cout << "修改成功后的建筑物信息:" << endl;
	print_Onebuilding(G, t_idx);

}

void change_edge(AdjGraph*& G)
{
	string st, ed;
	int  n, m;
	const double exp = 1e-6;
	while (true) {
		cout << "请输入要在哪两个地点之间修改边：";
		cin >> st >> ed;

		n = locate_vertexByName(G, st);
		m = locate_vertexByName(G, ed);
		//原则上必须加上n==-1 的特判,因为unsigned在与int进行比较的同时，就会强转为unsigned ,负数变为非常大的数
		if (n == m || n == -1 || m == -1 || G->adjlist.size() < n || G->adjlist.size() < m || locate_edgeById(G, n, m)) {
			cout << "输入有误，请重新输入！" << endl;
			continue;//这个非常重要，不然后面是有可能爆炸的，越界访问
		}
		else {
			break;
		}
		/*
		if (!locate_edgeById(G, n, m)) {//这条边确实存在
			break;
		}
		*/
	}
	double len_;
	int len;
	while (true) {
		cout << "请输入这条道路新的长度：";
		cin >> len_;
		len = int(len_);
		if (len < 0 || len == 0) {
			cout << "输入长度有误，请重新输入!" << endl;
			continue;
		}
		else if (len > 0) {
			break;
		}
	}
	ArcNode* ptr = G->adjlist[n].firstarc;
	while (ptr != nullptr) {
		if (ptr->adjvex == m) {
			ptr->weight = len;
			break;
		}
		ptr = ptr->nextarc;
	}
	ptr = G->adjlist[m].firstarc;
	while (ptr != nullptr) {
		if (ptr->adjvex == n) {
			ptr->weight = len;
			break;
		}
		ptr = ptr->nextarc;
	}
	//修改完成
}

void DispAdj(AdjGraph* G)
{
	int i;
	ArcNode* p;
	for (i = 0; i < G->ver_num; i++)
	{
		p = G->adjlist[i].firstarc;
		printf("%3d: ", i);
		while (p != NULL)
		{
			printf("%3d[%d]→", p->adjvex, p->weight);
			p = p->nextarc;
		}
		printf("∧\n");
	}
}

void show_buildings(AdjGraph* G)
{

	for (int i = 0; i < G->ver_num; i++) {
		const Vnode& p = G->adjlist[i];//常量指针
		cout << "=================================================" << endl;

		cout << "第" << i + 1 << "号建筑物名字是:" << p.data.name << endl;
		//打印星星
		cout << "推荐指数：";
		//int cnt=p.data.R_level  先不改   ☆★
		int cnt_int = int(p.data.R_level);
		int cnt_float = ceil(p.data.R_level) - cnt_int;
		for (int k = 0; k < cnt_int; k++)
			cout << "★";
		if (cnt_float == 1) cout << "☆";
		cout << endl;

		if (!p.data.eq_info.empty()) {
			cout << "它主要配备有：" << endl;
			for (auto t : p.data.eq_info)
				cout << t << endl;
		}
	}
}

void DestroyAdj(AdjGraph*& G)
{
	int i;
	ArcNode* pre, * p;
	for (i = 0; i < G->ver_num; i++)			//扫描所有的单链表
	{
		pre = G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre != NULL)
		{
			p = pre->nextarc;
			while (p != NULL)			//释放第i个单链表的所有边结点
			{
				free(pre);
				pre = p; p = p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}

void find_Building(AdjGraph* G)
{
	string name;
	int  idx;
	while (true) {
		cout << "请输入你想要查询的建筑名称或者建筑配备的信息：";
		cin >> name;
		idx = locate_vertexByName(G, name);
		if (idx != -1) {
			break;
		}
		idx = locate_vertexByEqInfo(G, name);
		if (idx != -1) {
			break;
		}
		cout << "你输入的名字有误，查无此建筑,请重新输入!" << endl;
	}
	cout << "查询到的该建筑相关信息如下:" << endl;
	print_Onebuilding(G, idx);
	cout << "=================================" << endl;

	cout << "查询结束，即将返回主操作界面" << endl;
	return;

}

void edit_Building(AdjGraph*& G)
{
	char mode;
	while (true) {
		cout << "请输入您想要进行的操作（1.添加建筑物 2.删除建筑物 3.修改建筑物及其配备信息 4.添加边（道路）5.删除边 6.修改边权值 7.退出操作）:" << endl;
		cin >> mode;
		//开始操作
		//int mode_ = mode - '0';
		switch (mode)
		{
		case '1':
			add_building(G);
			break;
		case '2':
			del_buildings(G);
			break;
		case '3':
			change_buildings(G);
			break;
		case '4':
			add_edge(G);
			break;
		case '5':
			del_edge(G);
			break;
		case '6':
			change_edge(G);
			break;
		case '7':
			cout << "正在退出编辑界面" << endl;
			return;
			break;
		default:
			cout << "输入有误，请重新输入!" << endl;
			break;
		}
	}

}

void dfs_all_path(int start, const int end, AdjGraph* G, bool visited[], vector<int>& path1, double path_exp, vector<MyPath>& ans)
{
	if (start == end) {//找到一个答案
		path1.push_back(start);
		MyPath ans_;
		ans_.dis = path_exp;

		for (int i = 0; i < path1.size(); i++) {//输出路径
			if (i != path1.size() - 1)
				ans_.road += G->adjlist[path1[i]].data.name + "——>";
			else
				ans_.road += G->adjlist[path1[i]].data.name;
		}
		//路径记录完毕，存入ans
		ans.push_back(ans_);
		path1.pop_back();
		visited[start] = false;
		return;
	}
	visited[start] = true;
	path1.push_back(start);

	ArcNode* ptr = G->adjlist[start].firstarc;//开始遍历所有的边
	while (ptr != nullptr) {
		int now = ptr->adjvex;//取出当前访问的节点编号
		if (!visited[now]) {
			path_exp += ptr->weight;
			dfs_all_path(now, end, G, visited, path1, path_exp, ans);
			path_exp -= ptr->weight;
		}
		ptr = ptr->nextarc;
	}
	//搜索完这一分支的所有情况
	path1.pop_back();
	visited[start] = false;
	return;

}

void dijkstra(AdjGraph*& G, int u, int v, string st, string ed) {//求出图中u-v的最短距离
	int dis[MAXV], DISpath[MAXV];
	bool book[MAXV];
	//初始化
	for (int i = 0; i < MAXV; i++)
		DISpath[i] = -1;
	memset(dis, 0x3f, sizeof dis);
	memset(book, false, sizeof book);
	//每次调用dijkstra() ,path会被覆盖
	ArcNode* ptr = G->adjlist[u].firstarc;
	while (ptr != nullptr) {
		DISpath[ptr->adjvex] = u;
		ptr = ptr->nextarc;
	}
	dis[u] = 0;

	priority_queue<PII, vector<PII>, greater<PII>> q;//使用堆优化,这个堆表示集合U 
	q.push({ 0,u });
	DISpath[u] = 0;
	while (q.size()) {
		auto t = q.top();//直接弹出不在集合S中的具有最小最短路径的节点
		q.pop();
		int now_node = t.second, distance = t.first;

		if (book[now_node])continue;//不在集合S中
		book[now_node] = true;//顶点now_node 加入集合S中，做标记

		//修改不在集合S中的顶点的最短路径
		ptr = G->adjlist[now_node].firstarc;
		while (ptr != nullptr) {
			int j = ptr->adjvex;
			if (!book[j] && dis[j] > distance + ptr->weight) {
				dis[j] = distance + ptr->weight;
				DISpath[j] = now_node;
				q.push({ dis[j],j });
			}
			ptr = ptr->nextarc;
		}
	}
	Dispath(dis, DISpath, u, v, G, st, ed);
}

void Dispath(int dis[], int path[], int u, int v, const AdjGraph* G, string st, string ed)//起点u---终点v
{
	int  j, k;
	int apath[MAXV];
	cout << "从建筑物" << st << "到建筑物" << ed << "的路径长为：" << dis[v] << endl;
	cout << " 路径为：";
	int d = 0;
	apath[d] = v;
	k = path[v];
	if (k == -1)
		printf("(。・＿・。)ﾉI’m sorry~，并没有为您找到满足目标的路线\n");
	else {
		while (k != u) {
			d++; apath[d] = k;
			k = path[k];
		}
		d++; apath[d] = u;//添加路径上的起点
		cout << G->adjlist[apath[d]].data.name;
		for (j = d - 1; j >= 0; j--)
			cout << "--->" << G->adjlist[apath[j]].data.name;
		printf("\n");
	}
}

vector<string> get_extra_aim(AdjGraph* G)
{
	string is_need;
	vector<string>  extra_aim;//出于节省空间开销，使用vector容器
	cout << "请问您是否想要再你的推荐路线中加入其它需要到达的地点（yes：需要 \tno或者其它输入指令：不需要）：" << endl;
	cin >> is_need;
	if (is_need._Equal("yes")) {//===============
		while (true) {
			string info, choice;
			cout << "请输入你想要在达到目标景点的路程中额外访问的景点名字：" << endl;
			cin >> info;
			if (locate_vertexByName(G, info) != -1) {
				extra_aim.push_back(info);
				cout << "添加成功!" << endl;
			}
			else {
				cout << "输入建筑物名字有误！温馨提醒，输入的是建筑物名字不是配备信息呐！" << endl;
			}
			//判断是否添加完毕
			cout << "是否以经添加完毕，若是，则输入yes，否则输入其它 !" << endl;
			cin >> choice;
			if (myStrcmp(choice, "yes")) break;
		}
	}
	return extra_aim;
}

void inquire_Building_Routes(AdjGraph* G)
{
	string st, ed;
	int  n, m;
	while (true) {
		cout << "请输入你要查询的起点景点名字：";
		cin >> st;
		cout << "请输入你要查询的终点景点名字：";

		cin >> ed;

		n = locate_vertexByName(G, st);
		n = (n != -1) ? n : locate_vertexByEqInfo(G, st);//如果使用者输入的是配备信息
		m = locate_vertexByName(G, ed);
		m = (m != -1) ? m : locate_vertexByEqInfo(G, ed);
		//原则上必须加上n==-1 的特判,因为unsigned在与int进行比较的同时，就会强转为unsigned ,负数变为非常大的数
		if (n == m || n == -1 || m == -1 || G->adjlist.size() < n || G->adjlist.size() < m) {
			cout << "输入景点有误，请重新输入！" << endl;
			continue;//这个非常重要，不然后面是有可能爆炸的，越界访问
		}
		else {
			break;
		}
	}
	char option;//使用字符串减少误触的麻烦，very good idea!
	cout << "请问你是否需要直接得到从" << st << "到" << ed << "的最短路径？还是需要添加额外的到达地点？" << endl;
	cout << "输入 1 直接得到最短路径 \t 输入2 继续添加额外目的地" << endl;
	while (true) {
		cout << "请输入您的选择:";
		cin >> option;
		if (option == '1' || option == '2') {
			break;
		}
		cout << "输入有误，请重新输入！" << endl;
	}

	//得到路径
	if (option == '1') {
		dijkstra(G, n, m, st, ed);
	}
	else {
		bool visited[MAXV] = { 0 };
		vector<int> path;//存储一条路
		vector<MyPath> path_ans;//存储所有道路
		double path_dis = 0;
		dfs_all_path(n, m, G, visited, path, path_dis, path_ans);
		//筛选路径：
		//筛选条件：
		vector<string>  extra_aim = get_extra_aim(G);//出于节省空间开销，使用vector容器

		vector<MyPath>::iterator it;
		int len = extra_aim.size();
		for (int i = 0; i < len; i++) {
			for (it = path_ans.begin(); it != path_ans.end();) {
				if (it->road.find(extra_aim[i]) == -1) {
					it = path_ans.erase(it);//删除元素，返回值指向已删除元素的下一个位置 
				}
				else {
					++it;//指向下一个位置
				}
			}
		}

		//打印路径
		if (path_ans.empty()) {
			cout << "没有从" << st << "到" << ed << "的路线存在" << endl;
			cout << "小trip ：可以尝试添加几条边（道路）之后再试哟！" << endl;
			return;
		}
		cout << "所有从" << st << "到" << ed << "的道路按距离远近升序排序后如下:" << endl;
		sort(path_ans.begin(), path_ans.end(), cmp);//排序

		for (int i = 0; i < path_ans.size(); i++) {
			if (path_ans.size() <= 10) {
				cout << "第" << i + 1 << "条道路为：" << path_ans.at(i).road << endl;
				cout << "距离是：" << path_ans.at(i).dis << endl;
			}
			else {
				cout << "为您推荐十条距离最短、满足需求的道路：" << endl;
				for (int i = 0; i < 10; i++) {
					cout << "第" << i + 1 << "条道路为：" << path_ans.at(i).road << endl;
					cout << "距离是：" << path_ans.at(i).dis << endl;
				}
				break;
			}
		}
	}
	cout << "查询道路结束，按任意键返回主操作界面" << endl;
	system("pause");
}


void dfs_hamidun(int i, AdjGraph* G, bool visited[], double path_exp, vector<int>& cur_path, vector<MyPath>& ans)
{
	cur_path.push_back(i);
	visited[i] = true;
	if (cur_path.size() == G->adjlist.size()) {//找到一个答案

		MyPath ans_;
		ans_.dis = path_exp;

		for (int i = 0; i < cur_path.size(); i++) {//输出路径
			if (i != cur_path.size() - 1)
				ans_.road += G->adjlist[cur_path[i]].data.name + "——>";
			else
				ans_.road += G->adjlist[cur_path[i]].data.name;
		}
		//路径记录完毕，存入ans
		ans.push_back(ans_);
		cur_path.pop_back();
		visited[i] = false;
		return;
	}

	ArcNode* ptr = G->adjlist[i].firstarc;//开始遍历所有的边
	while (ptr != nullptr) {
		int now = ptr->adjvex;//取出当前访问的节点编号
		if (!visited[now]) {
			path_exp += ptr->weight;
			dfs_hamidun(now, G, visited, path_exp, cur_path, ans);
			path_exp -= ptr->weight;
		}
		ptr = ptr->nextarc;
	}
	//搜索完这一分支的所有情况
	cur_path.pop_back();
	visited[i] = false;
	return;
}

void HaMiDun(AdjGraph*& G)
{
	vector<MyPath> ans;//存储一日游路线
	bool visited[MAXV] = { false };
	vector<int> cur_path;
	double path_exp = 0;
	for (int i = 0; i < G->adjlist.size(); i++) {
		cur_path.clear();
		memset(visited, false, sizeof visited);
		path_exp = 0;
		dfs_hamidun(i, G, visited, path_exp, cur_path, ans);
	}
	if (ans.empty()) {
		cout << "并不存在这样的路线" << endl;
		return;
	}

	sort(ans.begin(), ans.end(), cmp);//排序

	for (int i = 0; i < ans.size(); i++) {
		if (ans.size() <= 10) {
			cout << "第" << i + 1 << "条道路为：" << ans.at(i).road << endl;
			cout << "距离是：" << ans.at(i).dis << endl;
		}
		else {
			cout << "为您推荐十条距离最短、满足需求的道路：" << endl;
			for (int i = 0; i < 10; i++) {
				cout << "第" << i + 1 << "条道路为：" << ans.at(i).road << endl;
				cout << "距离是：" << ans.at(i).dis << endl;
			}
			char sat;
			cout << "以上路线是否如您意，还可以输入1显示全部一日游路线哟！,或者输入其它退出" << endl;
			cin >> sat;
			if (sat == '1') {
				cout << "全部一日游路线如下：" << endl;
				for (int i = 0; i < ans.size(); i++) {
					cout << "第" << i + 1 << "条道路为：" << ans.at(i).road << endl;
					cout << "距离是：" << ans.at(i).dis << endl;
				}
			}
			break;
		}
	}

	cout << "推荐一日游路线结束，按任意键返回主操作界面" << endl;
	system("pause");
}

void dfs_own_routes(int start, const int end, AdjGraph* G, bool visited[], double path_exp, vector<int>& cur_path, vector<MyPath>& ans, const double dis)
{

	cur_path.push_back(start);
	visited[start] = true;
	if (start == end && path_exp < dis) {//找到一个可能的答案
		MyPath ans_;
		ans_.dis = path_exp;

		for (int i = 0; i < cur_path.size(); i++) {//输出路径
			if (i != cur_path.size() - 1)
				ans_.road += G->adjlist[cur_path[i]].data.name + "——>";
			else
				ans_.road += G->adjlist[cur_path[i]].data.name;
		}
		//路径记录完毕，存入ans
		ans.push_back(ans_);
		cur_path.pop_back();
		visited[start] = false;
		return;
	}

	ArcNode* ptr = G->adjlist[start].firstarc;//开始遍历所有的边
	while (ptr != nullptr) {
		int now = ptr->adjvex;//取出当前访问的节点编号
		if (!visited[now]) {
			path_exp += ptr->weight;
			dfs_own_routes(now, end, G, visited, path_exp, cur_path, ans, dis);
			path_exp -= ptr->weight;
		}
		ptr = ptr->nextarc;
	}
	//搜索完这一分支的所有情况
	cur_path.pop_back();
	visited[start] = false;
}

void own_choose_routes(AdjGraph*& G)
{
	double distance;
	while (true) {
		cout << "请输入您认为合适的观赏路线长度（数字）:" << endl;
		cin >> distance;
		if (distance > 0) {
			break;
		}
		cout << "输入有误，请重新输入!" << endl;
	}
	string st, ed;

	int n = -1, m = -1;
	while (true) {
		cout << "请输入您的路线起点景点名字:" << endl;
		cin >> st;
		cout << "请输入你要路线终点景点名字：";

		cin >> ed;

		n = locate_vertexByName(G, st);
		n = (n != -1) ? n : locate_vertexByEqInfo(G, st);//如果使用者输入的是配备信息
		m = locate_vertexByName(G, ed);
		m = (m != -1) ? m : locate_vertexByEqInfo(G, ed);
		//原则上必须加上n==-1 的特判,因为unsigned在与int进行比较的同时，就会强转为unsigned ,负数会变为非常大的数
		if (n == m || n == -1 || m == -1 || G->adjlist.size() < n || G->adjlist.size() < m) {
			cout << "输入景点有误，请重新输入！" << endl;
			continue;//这个非常重要，不然后面是有可能爆炸的，越界访问
		}
		else {
			break;
		}
	}
	vector<string> extra = get_extra_aim(G);

	cout << "系统会尽可能推荐出满足您的观赏需求且距离不大于你输入的观赏路线长度的推荐旅游路线，请稍等!" << endl;
	vector<MyPath> ans;
	bool visited[MAXV] = { false };
	vector<int> cur_path;
	double path_exp = 0;
	dfs_own_routes(n, m, G, visited, path_exp, cur_path, ans, distance);//得到路线

	if (ans.empty()) {
		cout << "并不存在这样的路线" << endl;
		cout << "即将返回主界面！" << endl;
		return;
	}
	
	sort(ans.begin(), ans.end(), cmp);//排序
	vector<MyPath>::iterator it;
	int len = extra.size();
	for (int i = 0; i < len; i++) {
		for (it = ans.begin(); it != ans.end();) {
			if (it->road.find(extra[i]) == -1) {
				it = ans.erase(it);//删除元素，返回值指向已删除元素的下一个位置 
			}
			else {
				++it;//指向下一个位置
			}
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		if (ans.size() <= 10) {
			cout << "第" << i + 1 << "条道路为：" << ans.at(i).road << endl;
			cout << "距离是：" << ans.at(i).dis << endl;
		}
		else {
			cout << "为您推荐十条距离最短、满足需求的道路(按距离升序排序)：" << endl;
			for (int i = 0; i < 10; i++) {
				cout << "第" << i + 1 << "条道路为：" << ans.at(i).road << endl;
				cout << "距离是：" << ans.at(i).dis << endl;
			}
			break;
		}
	}

	cout << "推荐旅游路线结束，按任意键返回主操作界面" << endl;
	system("pause");
}

void Recommended_Guided_Routes(AdjGraph* G)
{
	char option;
	cout << "我们有二种路线方案供你选择:" << endl;
	cout << "1----一日游套餐，不重复游览民大所有建筑\t\t 2---自选推荐路线，根据您的路程距离、多个目标景点推荐" << endl;
	while (true) {
		cout << "请输入你的选择方案:" << endl;
		cin >> option;
		if (option == '1' || option == '2') {
			break;
		}
		cout << "输入有误，请重新输入:" << endl;
	}

	if (option == '1') {
		HaMiDun(G);
	}
	else if (option == '2') {
		own_choose_routes(G);
	}

}